#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//heap start from 0
#define PARENT(x) ((x-1)>>1)
#define LEFT(x) ((x<<1)+1)
#define RIGHT(x) ((x+1)<<1)
#define EXCHANGE(A,x,y) do{int temp=A[x]; A[x]=A[y]; A[y]=temp;}while(0)

int max_heapify(int *array, int len, int i)
{
	assert(array && len > 0);
	if(len < 2){
		return 0;
	}
	int k = i;
	while(1){
		if(LEFT(i) < len && array[i] < array[LEFT(i)]){
			k = LEFT(i);
		}
		if(RIGHT(i) < len && array[k] < array[RIGHT(i)]){
			k = RIGHT(i);
		}
		if(k != i){
			EXCHANGE(array, i, k);
			i = k;
		}else{
			break;
		}
	}
	return i;
}

int build_max_heap(int *array, int len)
{
	assert(array && len>0);
	int i;
	for(i=PARENT(len-1); i>=0; i--){
		max_heapify(array, len, i);
	}
	return 0;
}

int heap_sort(int *array, int len)
{
	build_max_heap(array, len);
	int i = 0;
	for(i=len-1; i>0; i--){
		EXCHANGE(array, 0, i);
		max_heapify(array, i, 0);
	}
	return 0;
}
